package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-07 01:32
 */
public class Pro1367 {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if(root == null) return false;
        return isSubPathFromRoot(head, root)|| isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    private boolean isSubPathFromRoot(ListNode head, TreeNode node) {
        if(head == null) return true;
        if(node == null) return false;
        if(node.val == head.val)
            return isSubPathFromRoot(head.next, node.left) || isSubPathFromRoot(head.next, node.right);
        return false;
    }

    ListNode head;
    boolean ans = false;
    public boolean isSubPath2(ListNode head, TreeNode root) {
        this.head = head;
        preOrder(root);
        return ans;
    }
    private void preOrder(TreeNode root) {
        if(root!= null) {
            if(root.val == head.val) {
                ListNode tmp = head;
                hasSubTreeList(root, tmp);
            }
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    private void hasSubTreeList(TreeNode root, ListNode node) {
        if(node == null) {ans = true; return;}
        if(root == null) return;
        if(root.val != node.val) return;
        hasSubTreeList(root.left, node.next);
        hasSubTreeList(root.right, node.next);
    }
}
